home *** CD-ROM | disk | FTP | other *** search
/ The X-Philes (2nd Revision) / The X-Philes Number 1 (1995).iso / xphiles / hp48hor2 / bmxl.doc < prev    next >
Text File  |  1995-03-31  |  11KB  |  321 lines
  1. (Comp.sys.hp48) 
  2. Item: 63 by seroussi at hplred.HP.COM 
  3. Author: [Gadiel Seroussi] 
  4.   Subj: BMXL - Binary Matrix Algebra Library 
  5.   Date: Sat Oct 19 1991 
  6.  
  7.  
  8.           BMXL - Binary Matrix Algebra Library V1.8 
  9.           =========================================== 
  10.  
  11. Appended at the end of this message are the uuencoded and ->ASC versions 
  12. of a library BMXL (lib number 1314). The library contains commands for 
  13. fast algebraic manipulation of binary matrices over the finite field 
  14. GF(2), i.e. under scalar addition and multiplication modulo 2 (XOR, 
  15. AND). These matrices and manipulations are useful in various areas of 
  16. applied mathematics, including coding theory, cryptography, graph 
  17. theory, and others. 
  18.  
  19.  
  20. Gadiel Seroussi 
  21. Hewlett-Packard Laboratories 
  22. Palo Alto, California 
  23.  
  24.  
  25.  
  26.  
  27. 1. MATRIX REPRESENTATION 
  28.    ===================== 
  29.  
  30. A binary matrix is represented by a list (we will sometimes refer to 
  31. this as a COMPACT representation of the matrix, as opposed to the 
  32. regular HP48 matrix representation). The first element of the list is a 
  33. real number (positive integer), representing the number of rows of the 
  34. matrix. The rest of the elements are binary integers, each representing 
  35. a COLUMN of the matrix. Rows and columns are indexed starting from zero. 
  36. Lower row indices correspond to lower significance bits in the binary 
  37. columns. Thus, entry (0,0) of the matrix is the least significant bit of 
  38. the first binary in the list. 
  39.  
  40. Example: the 4x5 binary matrix 
  41.  
  42.           1 0 0 1 0 
  43.      M =  1 1 1 1 1 
  44.           0 1 1 1 0 
  45.           1 1 0 0 0 
  46.  
  47. is represented by the list { 4 #Bh #Eh #6h #7h #2h }. 
  48.  
  49. When the matrix is square, the real number representing the number of 
  50. rows may be omitted. Thus, for example, the list { #Bh #Eh #6h #7h #2h } 
  51. represents the 5x5 matrix 
  52.  
  53.                 1 0 0 1 0 
  54.         M =     1 1 1 1 1 
  55.                 0 1 1 1 0 
  56.                 1 1 0 0 0 
  57.                 0 0 0 0 0 . 
  58.  
  59.  
  60. *** IMPORTANT LIMITATIONS:  
  61.  
  62. 1. In the current version of the library, all the binary numbers in the 
  63. list must be of word size 64, i.e. they must take exactly 13 bytes of 
  64. memory. Lists not complying with this restriction will be rejected by 
  65. the commands, with a "Bad Argument Value" error message. A command 
  66. (BFIX) is provided to "repair" a non-complying list. It is recommended 
  67. that binary word size be set to 64 when using the library. 
  68.  
  69. 2. The number of rows cannot exceed 64. The number of columns is, in 
  70. principle, limited only by the amount of available memory. However, some 
  71. commands will not accept matrices with more than 64 columns. 
  72.  
  73. The library provides commands that translate regular HP48 matrices 
  74. to/from the compact binary matrix representation, so matrices can be 
  75. entered using the HP48 MatrixWriter, and then converted to the compact 
  76. representation. Also, "viewers" are provided to display binary matrices 
  77. in the HP48 graphics environment. 
  78.  
  79. 2. IMPLEMENTATION 
  80.    ============== 
  81.  
  82. The library is written in a mixture of ML and system RPL. It was 
  83. developed using Jan Brittenson's STAR assembler, version 1.04.4. I 
  84. believe all system RPL entries used in the library are "supported" (from 
  85. the HP list). A few basic ML routines, however, are not "supported" (to 
  86. the best of my knowledge, there are no ML routines in the "supported" 
  87. list). These include routines for saving and restoring registers, 
  88. reading/writing shorts and binaries from/to the user stack, etc. 
  89.  
  90. The library has been extensively tested on my Rev-D HP48SX. However, no 
  91. guarantees are given that it will work on yours. 
  92.  
  93. Approximate timings: 
  94.  
  95.           Matrix 
  96.           dimensions     Inversion Multiplication 
  97.  
  98.           20x20          0.23 s         0.18 s 
  99.           50x50          1.00 s         0.64 s 
  100.  
  101. For comparison, for the same 20x20 matrix (interpreted as a real 
  102. matrix),  inversion on the HP48 takes 34.3 seconds. 
  103.  
  104. 3. DISCLAIMERS 
  105.    =========== 
  106.  
  107. This software is provided as is, without any warranty or assertion of 
  108. fitness for any purpose. This library makes use of undocumented and 
  109. unsupported features of the HP48. This might cause data loss or even 
  110. hardware damage. Use it at your own risk. 
  111.  
  112. Although I do work for Hewlett-Packard, the library was developed mostly 
  113. on my free time, and I have no relation with the Corvallis Division that 
  114. makes the calculator. They do not support, or even know about this 
  115. package. 
  116.  
  117. This software is placed in the public domain. It can be copied and 
  118. distributed freely, as long as (1) the package or any part of it are not 
  119. included in any package sold for profit, (2) all documentation and 
  120. credits are preserved. 
  121.  
  122. 4. LIBRARY COMMANDS 
  123.    ================ 
  124.  
  125. 4.1 Notation 
  126.     -------- 
  127.  
  128. The following notation will be used in the stack diagrams for the commands: 
  129.      %n   - a real number n. 
  130.      %0/1 - a real number valued 0/1. 
  131.      #0/1 - a binary integer valued 0/1. 
  132.      #b   - a binary integer. 
  133.      {M}  - a compact binary matrix, of dimensions r x c. 
  134.  
  135. When several input argument combinations are possible for a command, the 
  136. corresponding stack diagrams will be labeled (a), (b), (c), etc. 
  137.  
  138. 4.2 Commands 
  139.     -------- 
  140.  
  141. ABOUTBMX 
  142.      Displays current version, credits. 
  143.  
  144. BIDN 
  145.      %n        ->   {M} 
  146.  
  147.      Generates an identity matrix of order n. 
  148.  
  149. BZERO 
  150.     (a)   %n        ->   {M} 
  151.     (b)   { %n }         ->   {M} 
  152.     (c)   { %r %c }      ->   {M} 
  153.  
  154.      Generates  
  155.      (a,b) a zero matrix of order n, or  
  156.      (c) a zero matrix of dimensions rxc. 
  157.  
  158. BRAND 
  159.     (a)   %k        ->   #b 
  160.     (b)   { %n }         ->   {M} 
  161.     (c)   { %r %c } ->   {M} 
  162.  
  163.      Generates  
  164.      (a) a k-bit random binary number,  
  165.      (b) a nxn random binary matrix, or  
  166.      (c) a rxc random binary matrix. 
  167.  
  168. BMSHOW 
  169.      {M}       ->   {M} 
  170.  
  171.      Displays a binary matrix under the Graphics environment in 
  172.      "scrolling" mode. Leaves the matrix unchanged on the stack. 
  173.      *** The number of columns must be <= 64. 
  174.  
  175. BTSHOW 
  176.      {M}       ->   {M} 
  177.  
  178.      Like BMSHOW, but displays the transpose of the binary matrix. 
  179.      The number of columns of the input matrix is not limited. 
  180.      Leaves the input matrix unchanged on the stack. 
  181.  
  182. BVSHOW 
  183.      #b %n          ->   #b 
  184.  
  185.      Displays a binary integer as a binary row vector in the Graphics 
  186.      environment. The number of bits displayed is %n. The binary integer 
  187.      is left on the stack. 
  188.  
  189.      The row vector will be displayed with a "row index" of 0 to its 
  190.      left. This zero is not part of the vector. 
  191.  
  192. BTOM 
  193.      {M}       ->   Real Array 
  194.  
  195.      Converts a compact binary matrix to a regular HP48 2-dimensional 
  196.      array. 
  197.  
  198. MTOB 
  199.      Real Array     ->   {M} 
  200.  
  201.      Converts a regular HP48 2-dimensional array to a compact binary 
  202.      matrix. All nonzero entries are converted to 1. 
  203.  
  204. BADD 
  205.      {M}  {M}  ->   {M} 
  206.  
  207.      Adds two binary matrices. Addition is bitwise XOR. 
  208.  
  209. BMXM 
  210.      {M}  {M}  ->   {M} 
  211.  
  212.      Multiplies two binary matrices. 
  213.  
  214. BINV 
  215.      {M}       ->   {M}  1 
  216.      {M}       ->   0 
  217.  
  218.      Computes the inverse of a binary matrix, if it exists. Returns 
  219.      the inverse in level 2, and a real 1 in level 1 if the matrix is 
  220.      nonsingular, or a real 0 in level 1 otherwise. 
  221.  
  222. BTMX 
  223.      {M}       ->   {M'} 
  224.  
  225.      Computes the transpose of a binary matrix. 
  226.  
  227. BMXV  
  228.      {M} #b         ->   #b 
  229.  
  230.      Multiplies a binary matrix by a binary column vector. The column 
  231.      vector is represented by the binary #b, and it is assumed to be of 
  232.      dimension equal to the number of columns of the matrix. 
  233.  
  234. BVXM 
  235.      #b  {M}        ->   #b 
  236.  
  237.      Multiplies a binary row vector by a binary matrix. The row vector 
  238.      is represented by the binary #b, and it is assumed to be of 
  239.      dimension equal to the number of rows of the matrix. 
  240.  
  241. BRNK 
  242.      {M}       ->   %k 
  243.  
  244.      Computes the rank of a binary matrix. 
  245.  
  246. BSOLV 
  247.      {M} #y         ->   #x 
  248.  
  249.      Solves the linear equation M*x = y, where x and y are binary column 
  250.      vectors, if a solution exists (notice: only one solution will be 
  251.      found, even when many exist). 
  252.  
  253. BGAUS 
  254.      {M}       ->   {M1} #v %k 
  255.  
  256.      Performs Gaussian elimination on the columns of M. Returns a 
  257.      nonsingular matrix M1, of dimensions c x c,  such that M*M1 has 
  258.      unit vectors in rows corresponding to a maximal set of linearly 
  259.      independent rows of M. The binary #v has ones in positions 
  260.      corresponding to the same set of rows. %k is the rank of M. If M is 
  261.      nonsingular, M1 is the inverse of M. 
  262.  
  263. BNUL 
  264.      {M}       ->   {M1} 
  265.  
  266.      Computes a basis for the null space of the rows of M. M1 is a 
  267.      binary matrix of dimensions s x r and rank s, where s = r - 
  268.      rank(M), and M1*M = 0. 
  269.  
  270. BDIMS 
  271.      {M}       ->   { %r %c } 
  272.  
  273.      Return the dimensions of a binary matrix M. 
  274.  
  275. BGET 
  276.     (a)   #b %k          ->   %0/1 
  277.     (b)   {M} %j         ->   #b 
  278.     (c)   {M} { %i }     ->   #v 
  279.     (d)   {M} { %i %j }  ->   %0/1 
  280.  
  281.      Returns the value of  
  282.      (a) the k-th bit of a binary integer, 
  283.      (b) the j-th column #b of a binary matrix,  
  284.      (c) the i-th row #v of a binary matrix, or  
  285.      (d) the value of the (i,j)-th entry of a binary matrix. 
  286.  
  287.      *** NOTE: All indices start from zero. Valid indices are 
  288.      0 <= i <= r-1, 0 <= j <= c-1. 
  289.  
  290. BPUT 
  291.     (a)   #b %k %0/1     ->   #b 
  292.     (b)   #b %k #0/1     ->   #b 
  293.     (c)   {M} %j #b ->   {M1} 
  294.     (d)   {M} { %i } #v  ->   {M1} 
  295.     (e)   {M} { %i %j } %0/1 ->    {M1} 
  296.     (f)   {M} { %i %j } #0/1 ->    {M1} 
  297.  
  298.      Overwrites  
  299.      (a, b) the k-th bit of a binary integer,  
  300.      (c) the j-th column of a binary matrix,  
  301.      (d) the i-th row of a binary matrix, or  
  302.      (e, f) the value of the (i,j)-th entry of a binary matrix. 
  303.  
  304.      *** NOTE: All indices start from zero. Valid indices are 
  305.      0 <= i <= r-1, 0 <= j <= c-1. 
  306.  
  307. BFIX 
  308.      {list}         ->   {M} 
  309.  
  310.      "Fixes" a list that has binaries of lengths other than 16 nibbles 
  311.      (64 bits), but is otherwise a valid binary matrix. Also, inserts 
  312.      the number of rows if it was not in the list (the number of rows is 
  313.      assumed to be equal to the number of columns). 
  314.  
  315. BTRIM 
  316.      {M}       ->   {list} 
  317.  
  318.      Deletes the number of rows from a binary matrix, if it was there. 
  319.  
  320.      *** NOTE: Does not check that the matrix is square. 
  321.